package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/8
 * @description: 122. 买卖股票的最佳时机 II
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 */
public class A_122_买卖股票的最佳时机II {


	static A_122_买卖股票的最佳时机II action = new A_122_买卖股票的最佳时机II();

	public static void main(String[] args) {
//		test1();
		test2();
	}

	public static void test1() {
		// 7
		int[] prices = new int[]{7, 1, 5, 3, 6, 4};
		int res = action.maxProfit(prices);
		System.out.println("res = " + res);
	}

	public static void test2() {
		// 7
		int[] prices = new int[]{1, 2, 3, 4, 5};
		int res = action.maxProfit(prices);
		System.out.println("res = " + res);
	}

	/**
	 * 没想到这特么居然是个 简单题目！
	 * 是我孤陋寡闻了
	 * --
	 * 所谓的DP ，说到底是考虑所有的情况，不过会通过 数组存储中间计算结果，
	 * 便于 O(1) 的时间返回所需。
	 * 分析：
	 *
	 * @param prices
	 * @return
	 */
	public int maxProfit(int[] prices) {
		int len = prices.length;

		int[][] dp = new int[len][2];
		//dp[i][0] 表示 第i天持有股票 所得最大现金（即 最大利润）
		dp[0][0] = -prices[0];
		//dp[i][1] 表示 第i天不持有股票 所得最多现金（即 最大利润）
		dp[0][1] = 0;
		//这样的状态方程是可以完成描述操作流程的！
		for (int i = 1; i < len; i++) {
			//第i天持有股票 所得最多现金（要么保持 i-1 天的持股的最大现金，要么第 i-1 天卖出的最大现金）
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
			//第i天不持有股票 所得最多现金（1.将昨日 持有股票卖掉 or 2.保持不持股）
			dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
		}
		return dp[len - 1][1];
	}
}
